package com.cong.leetcode.offer26;

import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}


public class SubTreeStructure {
    public boolean isSubStructure(TreeNode A, TreeNode B) {

        if (A == null || B == null) {
            return false;
        }
        // 下面这段代码是使用栈进行先序遍历
        // Stack<TreeNode> stack = new Stack<>();
        // stack.push(A);
        // boolean res = false;
        // while(!stack.isEmpty()) {
        //     if (stack.peek().val == B.val) {
        //         boolean has = actureSubTree(stack.peek(), B);
        //         if(has) {
        //             return true;
        //         }
        //     }
        //     {
        //         TreeNode cur = stack.pop();
        //         if (cur.right != null) {
        //             stack.push(cur.right);
        //         }
        //         if (cur.left != null) {
        //             stack.push(cur.left);
        //         }
        //     }
        // }
        // return res;

        // 接下来使用递归进行先序遍历
        // TreeNode nextLayer = new TreeNode[] {A.left, A.right};
        return actrueSubTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean actrueSubTree(TreeNode tree, TreeNode subTree) {

        if (tree == null || tree.val != subTree.val) return false;
        boolean res = true;
        if (subTree.left != null) {
            res = actrueSubTree(tree.left, subTree.left);
        }
        if (subTree.right != null) {
            res &= actrueSubTree(tree.right, subTree.right);
        }
        List<Integer> list = null;
        list.stream().map((i) -> i + 1).toArray();
        StringBuilder sb = null;
        LinkedHashSet<Integer> s = null;

        return res;
    }
}